package haxe.util;

import haxe.util.LinkedList;
import haxe.util.Compare;
import haxe.util.Stack;

class SortedLinkedList<T> extends SortedCollection<T>
{
	private var _s:Int;
	private var _f:LEntry;
	private var _l:LEntry;
	
	public function new( c:Comparator<T> )
	{
		super(c);
		_s = 0;
	}
	
	public function add(o:T):Void
	{
		super.add(o);
		if ( _s > 0 )
		{
			if ( comp( o, _f.value ) <= 0 )
				addFirst(o);
			else if ( comp( o, _l.value ) >= 0 )
				addLast(o);
			else
			{
				var e:LEntry = _f;
				//linear implementation
				/*var n:LEntry = _l;
				while( comp( o, e.value ) > 0 && comp( o, n.value ) < 0 )
				{
					e = e.next;
					n = n.prev;
				}
				if ( comp( o, e.value ) <= 0 )
				{
					var tmp:LEntry = {prev:e.prev,next:e,value:o};
					e.prev.next = tmp;
					e.prev = tmp;
					++_s;
				}
				else if ( comp( o, n.value ) >= 0 )
				{
					var tmp:LEntry = {prev:n,next:n.next,value:o};
					n.next.prev = tmp;
					n.next = tmp;
					++_s;
				}//*/
				 
				//binary search alg
				e = bSE(o);
				var tmp:LEntry = {prev:e.prev,next:e,value:o};
				e.prev.next = tmp;
				e.prev = tmp;
				++_s;//*/
			}
		}
		else
		{
			_f = _l = { next:null,prev:null,value:o};
			_s = 1;
		}
		
	}
	
	public function indexOf(o:T):Int
	{
		var i:Int = 0;
		var e:LEntry = _f;
		while ( e != null && ! eq(o ,e.value) )// maybe equals method
		{
			e = e.next;
			++i;
		}
		return if ( eq(o, e.value) ) i else -1;
	}
	
	public function lastIndexOf(o:T):Int
	{
		var i:Int = _s - 1;
		var e:LEntry = _l;
		while ( e != null && ! eq(o ,e.value) )// maybe equals method
		{
			e = e.prev;
			--i;
		}
		return if ( eq(o ,e.value) ) i else -1;
	}
	
	public function iterator():Iterator<T>
	{
		return new ListIterator( _f );
	}
	
	public function clear():Void
	{
		_s = 0;
		_f = _l = null;
	}
	
	public function toArray():Array<T>
	{
		return Lambda.array( this );
	}
	
	public function isEmpty():Bool
	{
		return _s == 0;
	}
	
	public function remove(o:T, ?equals: T->T->Bool):Bool
	{
		var e:LEntry = _f;
		if ( equals == null ) equals = eq;
		while ( e != null && ! equals(e.value, o) )
		{
			e = e.next;
		}
		if ( equals(e.value, o) )
		{
			e.next.prev = e.prev;
			e.prev.next = e.next;
			--_s;
			return true;
		}else
			return false;
	}
	
	public function removeFirst():T
	{
		if ( _s > 0 )
		{
			var r:T = _f.value;
			_f = _f.next;
			#if neko
			if ( _s > 1 )//neko protes when null
			#end
			_f.prev = null;
			--_s;
			return r;
		}else
			return null;
	}
	
	public function removeLast():T
	{
		if ( _s > 0 )
		{
			var r:T = _l.value;
			_l = _l.prev;
			#if neko
			if ( _s > 1 )//neko protes when null
			#end
			_l.next = null;
			--_s;
			return r;
		}else
			return null;
	}
	
	public function getLast():T
	{
		return _l.value;
	}
	
	public function getFirst():T
	{
		return _f.value;
	}
	
	public function toString():String
	{
		return "SortedLinkedList";
	}
	
	public function removeAt(i:Int):T
	{
		if ( i > 0 && i < _s - 1 )
		{
			var e:LEntry = _f;
			while ( e != null && i > 0 )
			{
				e = e.next;
				--i;
			}
			if ( i == 0 )
			{
				var r:T =e.value;
				e.next.prev = e.prev;
				e.prev.next = e.next;
				--_s;
				return r;
			}else
			return null;
		}
		else if ( i == 0 )
			return removeFirst();
		else if ( i == _s - 1 )
			return removeLast();
		else
			return null;
	}
	
	public function contains(o:T, ?equals: T->T->Bool):Bool
	{
		var i:Int = 0;
		var e:LEntry = _f;
		var n:LEntry = _l;
		while ( e != null && ! eq(o ,e.value) && !eq(o ,n.value))
		{
			e = e.next;
			n = n.prev;
			++i;
		}
		return ( eq(o ,e.value) || eq(o ,n.value));
	}
	
	private function addFirst(o:T):Void
	{
		if ( _s > 0 )
		{
			_f.prev = {prev:null, next:_f, value:o};
			_f = _f.prev;
		}
		else
		{
			_f = _l = { next:null,prev:null,value:o};
		}
		++_s;
	}
	
	private function addLast(o:T):Void
	{
		if ( _s > 0)
		{
			_l.next = {next:null, prev:_l, value:o};
			_l = _l.next;
		}
		else
		{
			_f = _l = { next:null,prev:null,value:o};
		}
		++_s;
	}
	
	private function getSize():Int
	{
		return _s;
	}
	
	//unsafe - may run out of range ( returning null )
	private function getE(i:Int):LEntry
	{
		//if ( i >= 0 && i < _s )
		//{
			var e:LEntry;
			if ( _s - i - 1  > i )
			{
				e = _f;
				while ( i > 0 )
				{
					e = e.next;
					--i;
				}
			}
			else
			{
				e = _l;
				i = _s - i - 1;
				while ( i > 0 )
				{
					e = e.prev;
					--i;
				}
			}
			return e;
		//}else
		//	return null;
	}
	
	private function bSE(o:T):LEntry
	{
		var e:Int = _s-1;
		var b:Int = 0;
		var i:Int = ( e + b )>>1;
		var c:Int;
		var r:LEntry;
		while( e > b + 1 ) 
		{
			r = getE(i);
			c = comp( o, r.value );
			if ( c > 0 )
				b = i;
			else if ( c < 0 )
				e = i;
			else
				return r;
			i = ( e + b )>>1;
		}
		r = getE(b);
		return
		if ( comp( o, r.value ) > 0  )
		{
			r = getE(e);
			if ( comp( o, r.value ) < 0)
				r;
			else
				r.next;
		}else 
			r;
	}
	public static function main():Void
	{
		var N:Int = 5000;
		var getTime:Dynamic = 
		#if flash
			flash.Lib.getTimer;
		#else neko
			neko.Sys.time;
		#else js
			null;
		#end
		
		var list:SortedLinkedList<Int> = new SortedLinkedList(null);
		var stack:Stack<Int> = new Stack();
		for ( i in 0...N )
			stack.add(Math.round(Math.random()*N));
		var t = getTime();
		for ( i in stack )
		{
			list.add(i);
		}
		trace("Sorted List adding time : "+(getTime()-t));
		trace("Size:"+list.size);
		
		var t = getTime();
		while( !list.isEmpty())
			list.removeFirst();
		trace("Sorted List removing time : "+(getTime()-t));
	}
}